package com.example.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 *
 * @link { ht<a href="tps://leetcode.cn/problems/3sum">}</a>
 */
public class Code15 {
    public static void main(String[] args) {
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        Code15 code15 = new Code15();
        System.out.println(code15.threeSum(nums));

    }

    /**
     * 执行用时：2050 ms, 在所有 Java 提交中击败了5.03%的用户
     * 内存消耗：49.6 MB, 在所有 Java 提交中击败了5.03%的用户
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 边界问题
        if (nums == null || nums.length < 3) {
            return null;
        }
        Set<List<Integer>> ans = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            twoSum(nums, -nums[i], i, ans);
        }
        return new ArrayList<>(ans);
    }

    private void twoSum(int[] nums, int sum, int start, Set<List<Integer>> ans) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = start + 1; i < nums.length; i++) {
            if (map.containsKey(sum - nums[i])) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[start]);
                list.add(nums[map.get(sum - nums[i])]);
                list.add(nums[i]);
                list.sort(Comparator.comparingInt(i2 -> i2));
                ans.add(list);
            }
            map.put(nums[i], i);
        }
    }
}
